import collections
class Solution:
    def sortItems(self, n: int, m: int, group, beforeItems):
        node_edge = collections.defaultdict(set)
        group_edge = collections.defaultdict(set)
        group_du = collections.defaultdict(int)
        node_du = collections.defaultdict(int)
        group_dict = collections.defaultdict(set)
        for u, items in enumerate(beforeItems):
            group_1 = group[u]
            if group_1 != -1:
                group_dict[group_1].add(u)
            for v in items:
                group_2 = group[v]
                if group_2 != -1:
                    group_dict[group_2].add(v)
                if group_1 == -1:
                    if group_2 == -1:
                        group_edge[- v - 1].add(- u - 1)
                        group_du[- u - 1] += 1
                    else:
                        group_edge[group_2].add( - u - 1)
                        group_du[ - u - 1] += 1
                else:
                    if group_2 == -1:
                        group_edge[- v - 1].add(group_1)
                        group_du[group_1] += 1
                    else:
                        if group_1 != group_2:
                            if group_1 not in group_edge[group_2]:
                                group_edge[group_2].add(group_1)
                                group_du[group_1] += 1
                        else:
                            node_edge[v].add(u)
                            node_du[u] += 1
        group_st = set()
        ans = []
        for u, group_id in enumerate(group):
            if group_id == -1:
                group_id = - u - 1
            if group_du[group_id] == 0:
                group_st.add(group_id)
        while group_st:
            group_id = group_st.pop()
            if group_id < 0:
                ans.append(- group_id - 1)
            else:
                node_st = []
                for node in group_dict[group_id]:
                    if node_du[node] == 0:
                        node_st.append(node)
                while node_st:
                    node = node_st.pop()
                    ans.append(node)
                    for v in node_edge[node]:
                        node_du[v] -= 1
                        if node_du[v] == 0:
                            node_st.append(v)
            for v in group_edge[group_id]:
                group_du[v] -= 1
                if group_du[v] == 0:
                    group_st.add(v)
        if len(ans) == n:
            return ans
        else:
            return []

data = Solution()
# n = 8
# m = 2
# group = [-1,-1,1,0,0,1,0,-1]
# beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
# print(data.sortItems(n, m, group, beforeItems))
# n = 8
# m = 2
# group = [-1,-1,1,0,0,1,0,-1]
# beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
# print(data.sortItems(n, m, group, beforeItems))                
n = 5
m = 3
group = [0,0,2,1,0]
beforeItems = [[3],[],[],[],[1,3,2]]
print(data.sortItems(n, m, group, beforeItems))      



